//如何有效处理诸如手机号、英文单词等复杂元素的排序呢？仅仅靠一次计数排序很难实现。”

//这时候，我们不妨把排序工作拆分成多个阶段，每一个阶段只根据一个字符进行计数排序，一共排序k轮（k是字符串的长度）。

//把字符串元素按位拆分，每一位进行一次计数排序的算法，就是基数排序（Radix Sort）。”


// 假设我们只处理0-999范围内的整数数组
function radixSort(array) {
    // 获取数组中最大值的位数（假设都是正数）
    const maxLength = Math.max(...array.map(num => num.toString().length));

    // 从个位开始进行排序
    for (let digit = 0; digit < maxLength; digit++) {
        // 创建计数数组，用于统计每个桶中的元素数量
        const count = new Array(10).fill(0);

        // 计算每个元素在当前位上的数值，并更新计数数组
        for (let i = 0; i < array.length; i++) {
            const remainder = getDigit(array[i], digit);
            count[remainder]++;
        }

        // 将计数数组转换为前缀和数组，便于找到正确的位置插入元素
        for (let i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 创建一个新的临时数组存放已排序的结果
        const tempArray = new Array(array.length);

        // 逆序遍历原数组，根据计数数组计算新位置并放入临时数组
        for (let i = array.length - 1; i >= 0; i--) {
            const remainder = getDigit(array[i], digit);
            const sortedIndex = count[remainder] - 1;
            tempArray[sortedIndex] = array[i];
            count[remainder]--;
        }

        // 将临时数组的内容复制回原数组，准备下一轮排序
        array = [...tempArray];
    }

    return array;

    // 辅助函数：获取数字num在指定位数digit上的数字
    function getDigit(num, digit) {
        return Math.floor(Math.abs(num) / Math.pow(10, digit)) % 10;
    }
}

// 示例：
const numbers = [321, 234, 123, 987, 654, 456, 345, 234, 123, 0];
console.log(radixSort(numbers));
